use std::{
    collections::{btree_map::Keys, hash_map, linked_list, HashMap, LinkedList},
    fmt::Debug,
    hash::Hash,
};

pub struct LruCache<T, V>
where
    T: Eq + PartialEq + Hash + Clone,
{
    cache: LinkedList<T>,
    set: HashMap<T, V>,
    size: i32,
    maxsize: i32,
}
struct Iter<'a, K, V> {
    key: linked_list::Iter<'a, K>,
    map: &'a HashMap<K, V>,
}

impl<'a, K, V> Iterator for Iter<'a, K, V>
where
    K: Eq + Hash,
{
    type Item = (&'a K, &'a V);
    fn next(&mut self) -> Option<Self::Item> {
        match self.key.next() {
            Some(key) => unsafe {
                let val = self.map.get(key).unwrap();
                Some((key, val))
            },
            None => None,
        }
    }
}

impl<T, V> LruCache<T, V>
where
    T: Eq + PartialEq + Hash + Clone + Debug,
{
    fn new(size: i32) -> Self {
        LruCache {
            cache: LinkedList::new(),
            set: HashMap::new(),
            size: 0,
            maxsize: size,
        }
    }
    fn contains(&self, key: &T) -> bool {
        return self.set.get(key).is_some();
    }

    fn insert(&mut self, key: T, val: V) {
        if self.contains(&key) {
            self.remove(&key);
        }
        if self.size + 1 > self.maxsize && self.size > 0 {
            let top = self.cache.pop_front();
            self.set.remove(&top.unwrap());
            self.size -= 1;
        }
        self.set.insert(key.clone(), val);
        self.cache.push_back(key);
        self.size += 1;
    }
    fn remove(&mut self, key: &T) -> Option<V> {
        if self.contains(key) {
            let ret = self.set.remove(key);
            let mut idx = 0;
            for (i, v) in self.cache.iter().enumerate() {
                if v == key {
                    idx = i;
                }
            }
            //println!("before split{:?}", self.cache);
            let mut split = self.cache.split_off(idx);
            split.pop_front();
            //println!("debug{:?},split{:?}", self.cache, split);
            self.cache.append(&mut split);
            self.size -= 1;
            return ret;
        }
        None
    }

    fn get(&self, key: &T) -> Option<&V> {
        if self.contains(key) {
            let ret = self.set.get(key);
            return ret;
        }
        None
    }
    fn iter_key(&self) -> linked_list::Iter<'_, T> {
        self.cache.iter()
    }
    fn iter(&self) -> Iter<'_, T, V> {
        Iter {
            key: self.cache.iter(),
            map: &self.set,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        let test_arr = vec![1, 2, 3, 4, 5, 5, 6];
        let mut lru = LruCache::new(3);
        for i in 0..3 {
            lru.insert(test_arr[i], i);
        }
        lru.insert(test_arr[3], 3);
        if lru.contains(&1) {
            println!("unexcepted status 1 in");
        }
        // assert_eq!(lru.contains(&1), false);
        lru.insert(test_arr[4], 4);
        if lru.contains(&2) {
            println!("unexcepted status 2 in");
        }
        //assert_eq!(lru.contains(&2), false);
        lru.insert(test_arr[5], 5);
        if !lru.contains(&3) {
            println!("unexcepted status 3 not in");
        }
        //assert_eq!(lru.contains(&3), true);

        lru.insert(test_arr[6], 6);
        if lru.contains(&3) {
            println!("unexcepted status 3 in");
        }
        //assert_eq!(lru.contains(&3), false);
    }
    #[test]
    fn test_iter() {
        let arr = vec![1, 2, 3];
        let mut lru = LruCache::new(3);
        for v in arr {
            lru.insert(v, v);
        }
        for (idx, val) in lru.iter() {
            assert_eq!(idx, val);
        }
    }
}
